package org.kfive.nova.algorithm.binarytree;


/*
* BinarySearchTree.java
* Created  by  lizhanwu
* Created on 2016-7-22 16:41
* 二叉搜索树
*/
public class BinarySearchTree {

    private TreeNode root;

    public BinarySearchTree(){

    }

    public BinarySearchTree(TreeNode root){
        this.root = root;
    }

    /**
     * 二叉搜索树插入方法
     * @param value
     * @return
     */
    public boolean insert(int value){

        boolean isInserted = false;
        TreeNode p = root;
        while (p!=null){
            if(p.getValue()==value){
                return false;
            }
            p = p.getValue()<value?p.getLeftTree():p.getRightTree();
        }
        TreeNode tempNode = new TreeNode();
        tempNode.setValue(value);
        p = tempNode;
        isInserted = true;
        return isInserted;
    }

    /**
     * 二叉搜索树搜索方法
     * @param value
     * @return
     */
    public TreeNode search(int value){
        TreeNode p = this.root;
        while (p!=null){
            if(p.getValue()==value){
                break;
            }
            p = p.getValue()<value?p.getLeftTree():p.getRightTree();
        }
        return p;
    }

    /**
     * 二叉搜索树删除方法
     * @param value
     * @return
     */
    public boolean delete(int value){
        //删除标识
        boolean isDelete = true;
        TreeNode p = root;
        TreeNode parent = p;
        while (p!=null){
            if(p.getValue() == value){
                break;
            }
            parent = p;
            p = p.getValue()<value?p.getLeftTree():p.getRightTree();
        }
        //未找到删除节点
        if(p==null){
            isDelete = false;
        }else{
            if(p.getLeftTree()==null && p.getRightTree()==null){
                //判断是否是根节点
                if(p==root){
                    root = null;
                }else if(parent.getLeftTree().equals(p)){
                    parent.setLeftTree(null);
                }else {
                    parent.setRightTree(null);
                }
                //删除节点
                p = null;
            }else if(p.getLeftTree()!=null){
                if(p.equals(root)){
                    root = p.getLeftTree();
                }else if(parent.getLeftTree().equals(p)){
                    parent.setLeftTree(p.getLeftTree());
                }else{
                    parent.setRightTree(p.getLeftTree());
                }
                //删除节点
                p = null;
            }else if(p.getRightTree()!=null){
                if(p.equals(root)){
                    root = p.getRightTree();
                }else if(parent.getLeftTree().equals(p)){
                    parent.setLeftTree(p.getRightTree());
                }else {
                    parent.setRightTree(p.getRightTree());
                }
                //删除节点
                p = null;
            }else {
                TreeNode subRightTree = p.getRightTree();
                if(subRightTree.getLeftTree()==null){
                    parent.setRightTree(subRightTree.getRightTree());
                }else{
                    TreeNode tempParent = subRightTree;
                    while (subRightTree.getLeftTree()!=null){
                        tempParent = subRightTree;
                        subRightTree= subRightTree.getLeftTree();
                    }
                    p.setValue(subRightTree.getValue());

                    if(tempParent.getLeftTree().equals(subRightTree)){
                        p.setRightTree(subRightTree.getRightTree());
                    }else {
                        tempParent.setLeftTree(subRightTree.getRightTree());
                    }
                }
                subRightTree = null;
            }
        }
        return isDelete;
    }

}
